home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 412_01 / include / graph.h < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-29  |  2.6 KB  |  117 lines
  1. #ifndef _graph_H_
  2. #define _graph_H_
  3.  
  4. #include <stdio.h>
  5. #include "search.h"
  6. #include "bisearch.h"
  7. #include "nodes.h"
  8.  
  9.  
  10. /*                  BREADTH_GRAPH_
  11.  
  12.     This class implements a breadth first search algorithm, by generating
  13.     a search GRAPH. It is derived from class SEARCH_.
  14.  
  15. */
  16.  
  17. class BREADTH_GRAPH_ : public SEARCH_
  18. {
  19.     public:
  20.         BREADTH_GRAPH_(NODE_ *, NODE_ *, int);
  21.         int add(NODE_ *);
  22. };
  23.  
  24.  
  25.  
  26. /*                 DEPTH_GRAPH_
  27.  
  28.     This class implements a depth first search algorithm, by generating
  29.     a search GRAPH. It is derived from class SEARCH_.
  30.  
  31. */
  32.  
  33. class DEPTH_GRAPH_ : public SEARCH_
  34. {
  35.     public:
  36.         DEPTH_GRAPH_(NODE_ *, NODE_ *, int);
  37.         int add(NODE_ *);
  38. };
  39.  
  40.  
  41.  
  42. /*                       BIBREADTH_GRAPH_
  43.  
  44.     This class implements a bidirectional breadth first search algorithm,
  45.     by generating two search GRAPHs. It is derived from class BISEARCH_.
  46.  
  47. */
  48.  
  49. class BIBREADTH_GRAPH_ : public BISEARCH_
  50. {
  51.     public:
  52.         BIBREADTH_GRAPH_(NODE_ *, NODE_ *, int);
  53.         int add(SORTEDLIST_ *, SORTEDLIST_ *, NODE_ *);
  54. };
  55.  
  56.  
  57.  
  58. /*                    BIDEPTH_GRAPH_
  59.  
  60.     This class implements a bidirectional depth first search algorithm,
  61.     by generating two search GRAPHs. It is derived from class BISEARCH_.
  62.  
  63. */
  64.  
  65. class BIDEPTH_GRAPH_ : public BISEARCH_
  66. {
  67.     public:
  68.         BIDEPTH_GRAPH_(NODE_ *, NODE_ *, int);
  69.         int add(SORTEDLIST_ *, SORTEDLIST_ *, NODE_ *);
  70. };
  71.  
  72.  
  73.  
  74. /*                  BEST_
  75.  
  76.     This class implements a best first search algorithm. It is derived
  77.     from class SEARCH_ and processes nodes of class BEST_NODE_ (see bnode.h).
  78.     Classes that are derived from class BEST_NODE_ should have the following
  79.     functions:
  80.  
  81.     compute_g() : to compute the G-value of a node.
  82.     compute_h() : to compute the H-value of a node.
  83.  
  84. */
  85.  
  86. class BEST_ : public SEARCH_
  87. {
  88.     public:
  89.         BEST_(BEST_NODE_ *, BEST_NODE_ *, int);
  90.         int add(NODE_ *);
  91.         virtual int compute_g(const NODE_ &) = 0;
  92.         virtual int compute_h(const NODE_ &) = 0;
  93. };
  94.  
  95.  
  96.  
  97. /*               UNICOST_GRAPH_
  98.  
  99.     This class implements a uniform cost search algorithm, by generating
  100.     a search GRAPH. It is derived from class SEARCH_ and processes nodes
  101.     of class UNI_NODE_. Classes that are derived from class UNICOST_G_
  102.     should have the following function:
  103.  
  104.     compute_g() : to compute the G-value of a node.
  105.  
  106. */
  107.  
  108. class UNICOST_GRAPH_ : public SEARCH_
  109. {
  110.     public:
  111.         UNICOST_GRAPH_(UNI_NODE_ *, UNI_NODE_ *, int);
  112.         int add(NODE_ *);
  113.         virtual int compute_g(const NODE_ &) = 0;
  114. };
  115.  
  116. #endif
  117.